package com.xiyou.week04.bfs;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 200. 岛屿数量
 * <p>
 * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 * <p>
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 * <p>
 * 此外，你可以假设该网格的四条边均被水包围。
 *
 * @ClassName：NumIslands
 * @Author：西柚
 * @Date：2022/1/18 10:46 下午
 * @Versiion：1.0
 */
public class NumIslands {

    private static int m, n;
    private static boolean[][] visited;

    /**
     * 输入：grid = [
     * ['1','1','1','1','0'],
     * ['1','1','0','1','0'],
     * ['1','1','0','0','0'],
     * ['0','0','0','0','0']
     * ]
     * 输出：1
     *
     * @param grid
     * @return
     */
    public static int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;

        visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                visited[i][j] = false;
            }
        }

        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    ans++;
                    bfs(grid, i, j);
                }
            }
        }
        return ans;
    }

    private static void bfs(char[][] grid, int sx, int sy) {
        Queue<int[]> q = new LinkedList<int[]>();
        int[] dx = {-1, 0, 0, 1};
        int[] dy = {0, -1, 1, 0};
        q.add(new int[]{sx, sy});
        visited[sx][sy] = true;
        while (!q.isEmpty()) {
            // 第一步：取队头
            int x = q.peek()[0];
            int y = q.peek()[1];
            q.poll();
            // 第二步：扩展队头
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] != '1' || visited[nx][ny]) {
                    continue;
                }
                q.add(new int[]{nx, ny});
                visited[nx][ny] = true;
            }

        }
    }

    public static void main(String[] args) {
        char[][] grid = new char[][]{
                {'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}
        };
        System.out.println(numIslands(grid));
    }
}
